#include "lib.h"
#include "binary_tree.h"
void zero_one_pack(int *f,int weight,int value,int capacity)
{
	int ww;
	
	for (ww=capacity; ww>=weight; ww--) {
		if (f[ww] < (value + f[ww-weight])) {
			f[ww] = value + f[ww-weight];
		}
	}
}
int  zero_one_pack_problem(int *v,int *w, int n, int capacity)
{
	int i;
	int *f = NULL;
	int size = (capacity+1)*sizeof(int);

	f = (int *)malloc((size)*sizeof(int));
	for (i=0; i<size; i++) {
		f[i] = 0;
	}

	for(i=0; i<n;i++) {
		zero_one_pack(f,w[i],v[i],capacity);
	}

	i = f[capacity];
	free(f);
	return i;
}
void complete_pack(int *f,int weight,int value,int capacity)
{
	int ww;

	for (ww=weight; ww<=capacity; ww++) {
		if (f[ww] < (value + f[ww-weight])) {
			f[ww] = value + f[ww-weight];
		}
	}
}
int  complete_pack_problem(int *v,int *w, int n, int capacity)
{
	int i;
	int *f = NULL;
	f = (int *)malloc((capacity+1)*sizeof(int));

	for (i=0; i<=capacity; i++) {
		f[i] = 0;
	}

	for(i=0; i<n;i++) {
		complete_pack(f,w[i],v[i],capacity);
	}
	i = f[capacity];
	free(f);
	return i;
}

void  multiple_pack(int *f,int w,int v, int count, int capacity)
{
	int k = 1;

	if (count*w >= capacity) {
		complete_pack(f,w, v,capacity);
	} else {
		while (k < count) {
			zero_one_pack(f,w*k, v*k,capacity);
			count -=k;
			k *= 2;
		}
		zero_one_pack(f,w*count, v*count,capacity);
	}
}
int multiple_pack_problem(int *v,int *w, int *count_n,int n, int capacity)
{
	int i;
	int *f = NULL;

	f = (int *)malloc((capacity+1)*sizeof(int));

	for (i=0; i<=capacity; i++) {
		f[i] = 0;
	}

	for(i=0; i<n;i++) {
		multiple_pack(f,w[i], v[i],count_n[i],capacity);
	}
	i = f[capacity];
	free(f);
	return i;
}


int zero_one_pack_process(int *weight,int *value,int n,int capacity,int **process)
{
	int (*dp)[capacity+1];
	int i;
	int w;
	int gp[n+1][capacity+1];

	dp = process;

	memset(dp,0,sizeof(int)*(n+1)*(capacity+1));

	for (i=0; i<(n+1); i++) {
		gp[i][0] = 1;
	}
	for (i=0; i<(capacity+1); i++) {
		gp[0][i] = 1;
	}
	for (i=1;i<(n+1); i++) {
		for (w=weight[i-1]; w<=capacity; w++) {
			if (dp[i-1][w] < dp[i-1][w-weight[i-1]] + value[i-1]) {
				dp[i][w] = dp[i-1][w-weight[i-1]] + value[i-1];
				gp[i][w] = gp[i-1][w-weight[i-1]];
			} else if (dp[i-1][w] == dp[i-1][w-weight[i-1]] + value[i-1]) {
				gp[i][w] = gp[i-1][w-weight[i-1]] + gp[i-1][w];
				dp[i][w] = dp[i-1][w];
			} else {
				dp[i][w] = dp[i-1][w];
				gp[i][w] = gp[i-1][w];
			}
		}
		for (w=1; w<weight[i-1]; w++) {
			dp[i][w] = dp[i-1][w];
			gp[i][w] = gp[i-1][w];
			
		}
	}
	printf("group sum\n");
	two_dimension_array_print((int *)gp,n+1,capacity+1);
	return dp[n][capacity];
}

int zero_one_pack_path(int *weight,int *value,int n,int capacity,int **process)
{
	int (*dp)[capacity+1];
	int j = 0;
	
	printf("\nthe answer:\n");
	dp = process;
	while (capacity > 0 && n > 0) {
		if (dp[n][capacity] - dp[n-1][capacity-weight[n-1]] == value[n-1]) {
			capacity -= weight[n-1];
			printf("%d\t",weight[n-1]);
			j++;
		} 
		n--;
	}
	printf("\n");
	return  j;
}

int complete_pack_gp(int *weight,int n,int capacity)
{
	int gp[n+1][capacity+1];
	int i;
	int j;
	
	for (i=0; i<(n+1); i++) {
		gp[i][0] = 0;
	}
	for (i=0; i<(capacity+1); i++) {
		gp[0][i] = 0;
	}
	gp[0][0] = 1;
	for (i=1;i<(n+1); i++) {
	        for (j=0;j<=capacity; j++) {
		        if (j < weight[i-1])  {
		        	gp[i][j] =  gp[i-1][j];  
		        } else {  
		         	gp[i][j] =  gp[i-1][j] + gp[i][j-weight[i-1]]  ;
		        }
	        }
	}
	printf("group sum\n");
	two_dimension_array_print((int *)gp,n+1,capacity+1);
	return gp[n][capacity]  ;
}
int complete_pack_process(int *weight,int *value,int n,int capacity,int **process)
{
	int (*dp)[capacity+1];
	int i;
	int w;
	int gp[n+1][capacity+1];

	dp = process;

	memset(dp,0,sizeof(int)*(n+1)*(capacity+1));

	for (i=0; i<(n+1); i++) {
		gp[i][0] = 1;
	}
	for (i=0; i<(capacity+1); i++) {
		gp[0][i] = 1;
	}
	
	for (i=1;i<(n+1); i++) {
		for (w=1; w<weight[i-1]; w++) {
			dp[i][w] = dp[i-1][w];
			gp[i][w] = gp[i-1][w];
		}
		for (w=weight[i-1]; w<=capacity; w++) {
			if (dp[i-1][w] < dp[i][w-weight[i-1]] + value[i-1]) {
				dp[i][w] = dp[i][w-weight[i-1]] + value[i-1];
				gp[i][w] = gp[i][w-weight[i-1]];
			}else if (dp[i-1][w] == dp[i][w-weight[i-1]] + value[i-1]) {
				dp[i][w] = dp[i-1][w];
				gp[i][w] = gp[i-1][w] + gp[i][w-weight[i-1]];
			}else {
				dp[i][w] = dp[i-1][w];
				gp[i][w] = gp[i-1][w];
			}
		}
		
	}
	printf("group sum\n");
	two_dimension_array_print((int *)gp,n+1,capacity+1);
	return dp[n][capacity];
}

int complete_pack_path(int *weight,int *value,int n,int capacity,int **process)
{
	int (*dp)[capacity+1];
	int j = 0;

	printf("\nthe answer:\n");
	dp = process;
	while (capacity > 0 && n > 0) {
		if (dp[n][capacity] - dp[n][capacity-weight[n-1]] == value[n-1]) {
			capacity -= weight[n-1];
			printf("%d\t",weight[n-1]);
			j++;
		} else {
			n--;
		}
	}
	printf("\n");
	return  j;
}
void zero_one_pack_test(char **argv)
{
	int weight[] = {2,2,3} ;
	int value[] = {2,2,3};
	int capacity = atoi(argv[1]);
	int n = sizeof(weight)/sizeof(int);
	int process[n+1][capacity+1];
	int dp;

	array_print(weight,n, "weight");
	array_print(value,n, "value ");
	dp = zero_one_pack_process(weight,value,sizeof(weight)/sizeof(int),capacity,process);
	two_dimension_array_print((int *)process,sizeof(weight)/sizeof(int)+1,capacity+1);
	zero_one_pack_path(weight,value,sizeof(weight)/sizeof(int),capacity,process);
}
void complete_pack_test(char **argv)
{
	int weight[] = {1,2,5,10} ;
	int value[] = {1,2,5,10};
	int capacity = atoi(argv[1]);
	int n = sizeof(weight)/sizeof(int);
	int process[n+1][capacity+1];
	int dp;

	array_print(weight,n, "weight");
	array_print(value,n, "value ");
	complete_pack_gp(weight,n,capacity);
	
	dp = complete_pack_process(weight,value,sizeof(weight)/sizeof(int),capacity,process);
	two_dimension_array_print((int *)process,sizeof(weight)/sizeof(int)+1,capacity+1);
	complete_pack_path(weight,value,sizeof(weight)/sizeof(int),capacity,process);
	
}
int main(int argc, char **argv)
{
	complete_pack_test(argv);
	//zero_one_pack_test(argv);
	return 0;
}
